package sort;

import java.util.Arrays;
import java.util.Objects;

/**
 * 归并排序
 *
 * @author Ringo
 * @date 2022/3/16 19:55
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] a = {1, 3, 1, 4, 1, 5, 9, 2, 6, 5, 8, 9};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void mergeSort(int[] a) {
        if (Objects.isNull(a) || a.length < 2) return;
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + ((hi - lo) >> 1);
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    private static void merge(int[] a, int lo, int mid, int hi) {
        // 开的这个临时数组长度应该为 hi-lo+1
        int[] temp = new int[hi - lo + 1];
        int i = lo, j = mid + 1;
        int k = 0;

        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) temp[k++] = a[i++];
            else temp[k++] = a[j++];
        }
        while (i <= mid) temp[k++] = a[i++];
        while (j <= hi) temp[k++] = a[j++];

        // 将临时数组的中数拷贝回原数组
        for (i = 0; i < k; ++i) {
            a[lo + i] = temp[i];
        }
    }
}
